\section{A Distributed Filesystem}
\label{filesystem}

Similar to the Ceph object based filesystem \cite{Weil:2006p1292}, also developed at UCSC, Ringer separates out the handling of data and metadata through node specialization. 
%% NOTE: Make sure to discuss further in related work section; centralized metadata server, broadcast search via homogeneous local peers, Ringer
This is in sharp contrast to most P2P networks which use uniform nodes. 
Ceph differentiates data and metadata to allow for scalable numbers of parallel metadata operations, and also to support a pseudo-random object placement scheme (CRUSH). 
Conversely, Ringer uses node specialization to facilitate search rather than performance. 
Virtual metadata nodes add structure to the Ringer topology while creating a secondary connectivity graph, allowing clients to find one another quickly.

We first focus on the client filesystem, followed by the metadata servers (MDS).
We then show how these pieces interact to produce coherent reads and writes.

\subsection{Client}

%%As discussed, 
The Ringer client is implemented via the FUSE library as a mountable local volume.
Data is stored in a shadow directory which is unique to each user.
Each client connects to (registers with) only one MDS.
This MDS is known as the ``owning" MDS and is passed via a configuration file or command line parameter to the client at initialization time.
All metadata lookups are sent to this single MDS.
In practice, this involves translating from the native Unix ``struct stat'' structure to Ringer's metadata objects (dubbed ``rnodes")  and vice-versa.
Data is transfered directly between clients in blocks. 
Currently a 4K block-size, the native block-size of FUSE, is used. 
%% NOTE: leases is undefined at this point in the paper, this may be okay
%Increasing the block-size would decrease the number of read and write leases needed to process a file and could lead to a performance increase. %% EXPERIEMENT
Clients are identified by a client id, consisting of a host and port pair, which is unique to each user.
Therefore, more than one Ringer volume may be simultaneously mounted on a single physical system.

Files are owned by only the one client which created that file. 
In order to simplify implementation, ownership cannot be transferred.
A client is responsible for registering newly created files with that client's MDS.

Ringer supports both a synchronous and an asynchronous communication protocol for data transfer.
A client may contact another client and ask for a block of data from a file.
The requesting client blocks until the data is sent back.
Alternatively, a client \emph{or MDS} may contact a client and request that a block of data be sent to a specified host.
The requested block is sent to the noted recipient and handled by a separate callback function.
The recipient may be the client making the request or a third party. 
For example, a MDS may realize that a client's cached data is invalid and send a request to update the data.
In this form, the requested block is sent to the noted recipient and handled by a separate callback function.

\subsection{Metadata Server}

The MDS maintains a list of registered clients, and can connect to an unlimited number of parent MDSs as a client  MDS via the same protocol clients use to connect to their owning MDS.
Ancestor MDSs know which files (via an in memory hash table of Ringer paths) their descendent MDSs own, but do not store more detailed file metadata.
Since MDSs can have arbitrarily many parents, the MDS graph for a particular network can be as complete or sparse as desired.
%In practice, we have only experimented with tree structured MDS graphs.

When a client owns a file, the client's MDS owns the rnode for that file
%Rnodes encapsulate all information about a file, so that file metadata exists in only one place.

\subsection{Single Namespace}
\label{single-namespace}

Ringer paths are globally unique for each file.
They are formed by appending the owning client's client id to the file path.
Some path mangling is required to translate ringer paths to locally understandable paths, but we feel that the simplicity of unique paths outweighs the additional translation logic.

This global namespace can be traversed as follows:
In the root of each Ringer volume, a .hosts directory exists. 
The .hosts directory contains a set of directories corresponding to all of the clients connected to the local client's owning MDS, the local client's owning MDS's children and the local client's owning MDS's parents.
In the case of a binary tree structured MDS graph, there would be clients from at most 4 MDSs in one .hosts file.
Each client is mounted inside its directory. 
Note that a path of the form 
{\tt .hosts/client\_id1/.hosts/client\_id2/foo} 
is the same to Ringer as 
{\tt client\_id2/foo}.
Long path names are simplified automatically.
Clients further away in the topology (for example, associated with a grandparent MDS) can be accessed via a chain of intermediate clients.

\subsection{Reads}

Close-to-open consistency is maintained by a system of leases, arbitrated by the MDS which owns the rnode for the file under consideration.

When a client wishes to read a file, it must request a read lease from the MDS which owns the rnode of that file.
The client initially sends the request to the owning MDS of that client, which then finds the correct MDS by successively checking with parent MDSs until some ancestor recognizes the file. 
This ancestor MDS forwards the request to the MDS which actually owns the file. 
The owning MDS checks file permissions, decides whether or not to grant the lease and passes back permission (or denial) down the chain of intermediate MDSs.
Read leases are always granted to clients with read permission, except when another client has a current write lease for the file. 
Note that leases operate on the file (not block) level.
If a read lease is not granted, the client may try again after a few moments.

To eliminates the lookup overhead when a file is repeatedly accessed, each client maintains a cache of known filenames and their associated MDSs.
%Once the owning MDS of a file is known, that information is cached for future use. 

If granted a read, the requesting client first downloads the rnode for that file. 
Rnodes maintain a ``last modified" date for the associated file; there is no caching of rnodes.
The requesting client then checks to see if the last modified date matches the date for any locally cached relevant blocks.
If the last modified dates differ or the file has not yet been read, the requesting client contacts the owning client directly and downloads the requested blocks.
%% NOTE: One drawback is that modifying one block of a file will invalidate cached copies of all blocks. We could granularize the last modified dates further.
The owning client's IP address and port are listed in the rnode for the file.

Leases do not time out quickly; they should be explicitly terminated by the leaseholder. 
Whenever the client's {\tt read()} system call ends, the {\tt endRead()} function is invoked.
This function contacts the owning metadata server for the file, and requests lease termination.
The call is asynchronous, returning without waiting for a response from the MDS.

One performance improvement would be maintaining read leases beyond one {\tt read()} call. 
This optimization would not change the overall Ringer protocol however.

\subsection{Writes}

Writes follow the same protocol as reads, with one important difference. 
Only one client can have the lease for a file at any given time, if that lease is a write lease. 
When a write lease is requested, the MDS only grants the lease if there are no outstanding read leases for the file.
Because leases are short lived, clients busy-wait until a write lease is granted. 
The duration of the write lease is the duration of the client's {\tt write()} system call.

%% NOTE: it would be nice if there was some sort of optional consistency checking here. If clients want to read-modify-write, they may not wish to make the final write if the file has been modified intermediately. After granting the lease, the last modified date could be checked.


